package com.xiaoyu.binarySearch;

import java.util.*;

/**
 * @program: DS_and_A
 * @description:
 * 第一题:
 * 给定两个数组，编写一个函数来计算它们的交集。
 *
 * 输入：nums1 = [1,2,2,1], nums2 = [2,2]
 * 输出：[2]
 *
 *
 * 第二题:
 * 给定两个数组，编写一个函数来计算它们的交集。
 * 输入：nums1 = [1,2,2,1], nums2 = [2,2]
 * 输出：[2,2]
 *
 * 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
 * 输出：[4,9]
 *
 * 输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
 *
 * @author: YuWenYi
 * @create: 2021-05-06 08:55
 **/

public class Intersection {
    //第一题:
    //解法一:排序+二分查找  --> 自己的解法
    public static int[] intersection1(int[] nums1, int[] nums2) {
        //将num1数组进行排序,用以后续的二分查找
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        //使用集合方便保存结果,并使用有参构造避免扩容
        ArrayList<Integer> resList = new ArrayList<>(Math.min(nums1.length, nums2.length));

        //尽量去遍历长度较小的那个数组...这个影响不是很大
        int[] temp;
        if (nums1.length < nums2.length){
            temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

        int p2 = 0;  //num2数组的指针

        int left = 0;  //num1数组的左边界
        int right = nums1.length; //num1数组的右边界
        while (p2<nums2.length){  //遍历整个num2数组
            int mid = (left + right)/2;
            if (nums1[mid] == nums2[p2]){  //查找两个数组是否存在相同值,即并集
                if (!resList.contains(nums2[p2])){  //避免并集重复
                    resList.add(nums2[p2]);  //自动装箱,加入集合
                }
                //这就代表这已经找到了一个并集值了,即此次循环结束
                //那么就使p2++,重置左右指针,重新二分该num1,继续找下一个并集值
                p2++;
                left = 0;
                right = nums1.length;
            }else if (nums1[mid] > nums2[p2]){
                right = mid;
            }else {
                left = mid + 1;
            }
            if (left >= right){
                //如果left == right 那么代表此次循环未找到并集,则重置左右指针进入下一次循环
                p2++;
                left = 0;
                right = nums1.length;
            }
        }
        //使用了流的方法让这个集合转换成一个int数组
        return resList.stream().mapToInt(Integer::valueOf).toArray();
    }

    //解法二:充分利用set集合的不可重复性(更优解)
    public static int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();

        for (int i : nums1) {
            set1.add(i);
        }

        for (int i : nums2) {
            //只保存set1中有的值
            if (set1.contains(i)){
                set2.add(i);
            }
        }
        int[] res = new int[Math.min(set1.size(), set2.size())];

        int j = 0;
        for (Integer i : set2) {
            res[j++] = i;
        }
        return res;
    }


    //第二题:元素在两个数组中出现次数的最小值一致,这里是最难的
    //解法一:排序 + 双指针
    public static int[] intersect1(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int p1 = 0,p2 = 0;
        int[] resTemp = new int[Math.min(nums1.length, nums2.length)];
        int index = 0;
        while (p1 < nums1.length && p2 < nums2.length){
            if (nums1[p1] == nums2[p2]){
                resTemp[index++] = nums1[p1];
                p1++;
                p2++;
            }else if (nums1[p1] > nums2[p2]){
                p2++;
            }else {
                p1++;
            }
        }
        //System.arraycopy(resTemp, 0, res, 0, index);
        return Arrays.copyOfRange(resTemp, 0, index);
    }

    //解法二:使用哈希表
    public static int[] intersect(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> map = new HashMap<>();
        //将num1放入哈希表中
        for (int i : nums1) {
            /*
            高级用法:
            //getOrDefault:如果获取到了get(i)的值,就获取它,如果没有获取到,就使用自定义的默认值

            int count = map.getOrDefault(i, 0) + 1;
            map.put(num, count);
            */
            if (map.containsKey(i)){
                map.put(i,map.get(i) + 1);
            }else {
                map.put(i,1);
            }
        }
        int[] res = new int[Math.min(nums1.length, nums2.length)];
        int index = 0;
        for (int i : nums2) {
            if (map.containsKey(i) && map.get(i)>0){
                res[index++] = i;
                map.put(i,map.get(i) - 1);
            }
        }
        return Arrays.copyOfRange(res, 0, index);
    }

    public static void main(String[] args) {
        int[] nums1 = new int[]{9,4,9,8,4};
        int[] nums2 = new int[]{4,9,4,5,2};
        int[] ints = intersect(nums1, nums2);

        System.out.println(Arrays.toString(ints));
    }

}
